/*
对于任意的真分数 N/M （ 0 < N < M ），均可以求出对应的小数。如果采用链表存储各位小数，对于循环节采用循环链表表示，则所有分数均可以表示为如下链表形式。

![](图片1)

输入： N M

输出： 整个循环节

要求：
 编写一个尽可能高效的查找循环节起始点的函数： NODE * find( NODE * head, int * n ) 。函数的返回值为循环节的起点（即图中的指针p），n为循环节的长度。

说明：提交程序时请同时提交将分数转换为小数的函数 change( int n, int m, NODE * head ) （前面题目中已经编写）。
*/

/*
测试用例1:
输入：
1 3↵
输出：
ring=1↵
3↵

测试用例2:
输入：
1 8↵
输出：
ring=0↵
NULL↵

测试用例3:
输入：
29 33↵
输出：
ring=2↵
87↵

测试用例4:
输入：
2 7↵
输出：
ring=6↵
285714↵
*/

// 预设代码
/* PRESET CODE BEGIN - NEVER TOUCH CODE BELOW */  
 
#include <stdio.h>
#include <stdlib.h>
typedef struct node
{
    int data;
    struct node * next;
} NODE;
  
NODE * find( NODE * , int * );
void outputring( NODE * );
void change( int , int , NODE * );

// 打印循环节
void outputring( NODE * pring )  
{
    NODE * p;
    p = pring;
    if ( p == NULL )
        printf("NULL");
    else
        do {
            printf("%d", p->data);  
            p = p->next;  
        } while ( p != pring );
  
    printf("\n");
    return;
}
  
int main()
{   
    int n, m;
    NODE * head, * pring;
  
    scanf("%d%d", &n, &m);  
    head = (NODE *)malloc( sizeof(NODE) );  
    head->next = NULL;  
    head->data = -1;  
    
    // 依据分数，创建链表，n记录循环节长度
    change( n, m, head );
    
    // 查找循环节，返回循环节头节点
    pring = find( head, &n );
    
    // 打印循环节长度
    printf("ring=%d\n", n);
    
    outputring( pring );
  
    return 0;
}
  
#include<vector>
using namespace std;

int find_id(int e, int n, vector<int> quotients, vector<int> remainders);
NODE * find_node(NODE * head, int id);

// 依据除法，创建列表
void change( int n, int m, NODE * head ) 
{
    // 记录商
    int e;
    
    // 记录索引
    int id;
    
    // 辅助节点
    NODE * p = head;
    
    // 记录各个阶段的 商、余数
    vector<int> quotients;
    vector<int> remainders;
    
    while(true)
    {
        n = 10 * n;
        e = n / m; // 商
        n = n % m; // 余数
        
        id = find_id(e, n, quotients, remainders);
        
        if (id == -1)
        {
            // 记录商、余数
            quotients.push_back(e);
            remainders.push_back(n);
            
            // 添加节点
            NODE * new_node = new NODE;
            new_node->data = e;
            new_node->next = NULL;
            
            p->next = new_node;
            p = p->next;
        }
        else
        {
            // 依据索引，查找链表中的节点
            NODE * node = find_node(head, id);
            
            // 连接
            p->next = node;
            
            break;
        }
        
        // 被整除
        if (n == 0) break;
          
    }
}
 
NODE * find( NODE * head, int * n ) 
{
    /* 找到循环节的长度*/
    NODE * fast_p = head;
    NODE * slow_p = head;
    int i = 0; // 记录长度
    
    while(true)
    {
        // 快指针移动两步
        for(int j=0;j<2;j++)
        {
            fast_p = fast_p->next;
            if (fast_p == nullptr)
            {
                *n = 0;
                return NULL;
            }
        }
        
        // 慢指针移动一步
        slow_p = slow_p->next;
        
        i++;
        
        // 两个指针相遇
        if (fast_p == slow_p)
        {
            *n = i;
            break;
        }
    }
    
    /* 找到循环节的头节点 */
    // 循环节长度
    int ring_len = *n;
    
    // 设置两个指针，相距 ring_len，相遇时，即到循环节的头节点
    NODE * pring = head;
    
    NODE * tail = head;
    for (int i=0; i<ring_len; i++) 
        tail = tail->next;
    
    while(pring != tail)
    {
        pring = pring->next;
        tail = tail->next;
    }
    
    return pring;
}

// 查找商、余数是否记录在案，如果记录在案，返回索引，否则返回-1
int find_id(int e, int n, vector<int> quotients, vector<int> remainders)
{
    for (int i=0; i<quotients.size(); i++)
    {
        if (e == quotients[i] && n == remainders[i])
            return i;
    }
    return -1;
}

// 依据索引，查找链表中的节点
NODE * find_node(NODE * head, int id)
{
    NODE * p = head;
    
    for (int i=0; i<=id; i++) 
        p = p->next;
    return p;
}
/* PRESET CODE END - NEVER TOUCH CODE ABOVE */ 